#include <iostream>
#include "bitree.cpp"
#define NEW_NODE (BiTNode *)malloc(sizeof(BiTNode))

using namespace std;

Status judge(TElemType e)
{
	static int last_element;
	static bool first_called = true, is_BST = true;
	if(e == ~0)
		return is_BST;
	if(first_called == true)
	{
		first_called = false;
	}
	else
	{
		if(last_element > e)
			is_BST = false;
	}
	last_element = e;
	return OK;
}

bool is_BST(BiTree tree)
{
	tree.InOrderTraverse(judge);
	return judge(~0);
}

Status print(TElemType e)
{
	cout << e << " ";
	return OK;
}

int main()
{
	BiTree tree;
	BiTNode *temp;
	Status st;

	temp = NEW_NODE;
	temp->data = 2;
	temp->lchild = temp->rchild = temp->parent = NULL;
	st = tree.InsertChild(NULL, 0, temp);

	temp = NEW_NODE;
	temp->data = 1;
	temp->lchild = temp->rchild = temp->parent = NULL;
	st = tree.InsertChild(tree.Root(), 0, temp);

	temp = NEW_NODE;
	temp->data = 4;
	temp->lchild = temp->rchild = temp->parent = NULL;
	st = tree.InsertChild(tree.Root(), 1, temp);
	BiTNode *left, *right;
	left = tree.LeftChild(tree.Root());
	right = tree.RightChild(tree.Root());
	
	temp = NEW_NODE;
	temp->data = 3;
	temp->lchild = temp->rchild = temp->parent = NULL;
	tree.InsertChild(right, 0, temp);

	temp = NEW_NODE;
	temp->data = 5;
	temp->lchild = temp->rchild = temp->parent = NULL;
	tree.InsertChild(right, 1, temp);
	cout << "Traverse: ";
	tree.InOrderTraverse(print);
	cout << endl << "The tree is " << (is_BST(tree)?"":"not ") << "a BST."<< endl; 
	right->data = 6;
	cout << "Traverse: ";
	tree.InOrderTraverse(print);
	cout << endl << "The tree is " << (is_BST(tree)?"":"not ") << "a BST."<< endl; 
	return 0;
}
/*
第一棵树：
2
|\
1 4
  |\
  3 5

第二棵树：
2
|\
1 6
  |\
  3 5
就这样吧- -
*/